|
In computer science, the subset sum problem is one of the important problems in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set , the answer is ''yes'' because the subset sums to zero. The problem is NP-complete. An equivalent problem is this: given a set of integers and an integer ''s'', does any non-empty subset sum to ''s''? Subset sum can also be thought of as a special case of the knapsack problem. One interesting special case of subset sum is the partition problem, in which ''s'' is half of the sum of all elements in the set. == Complexity == The complexity of the subset sum problem can be viewed as depending on two parameters, ''N'', the number of decision variables, and ''P'', the precision of the problem (stated as the number of binary place values that it takes to state the problem). (Note: here the letters ''N'' and ''P'' mean something different from what they mean in the NP class of problems.) The complexity of the best known algorithms is exponential in the smaller of the two parameters ''N'' and ''P''. Thus, the problem is most difficult if ''N'' and ''P'' are of the same order. It only becomes easy if either ''N'' or ''P'' becomes very small. If ''N'' (the number of variables) is small, then an exhaustive search for the solution is practical. If ''P'' (the number of place values) is a small fixed number, then there are dynamic programming algorithms that can solve it exactly. Efficient algorithms for both small ''N'' and small ''P'' cases are given below. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Subset sum problem」の詳細全文を読む スポンサード リンク
|